基于随机投影的大规模网络社区检测算法
亓颢博，北京师范大学统计学院师资博士后。毕业于北京大学光华管理学院商务统计与经济计量系，获经济学博士学位。主要研究方向包括统计优化算法、大规模数据统计建模、网络结构数据分析等。 在 Journal of Computational and Graphical Statistics、Neurocomputing、Computational Statistics & Data Analysis 等统计学与计算机期刊发表多篇论文。
今天要跟大家分享的主题是基于随机投影的大规模网络社区检测算法。内容主要包括社区检测的简要背景介绍，基于随机投影的社区检测算法的介绍以及理论性质。
1. 背景介绍
随着人们收集数据、分析数据的能力不断提升，大数据时代无可避免的到来。在数据量大大增加的同时，人们研究的数据种类也在不断扩充。其中，网络数据(Network Data)依托各种各样社交网络、物联网等等实际应用平台大量产生，而它的独特结构和性质也受到了学者们越来越多的关注。而在网络分析中，社区检测(Community Detection)是一个十分重要的基础性问题。
通常我们会用网络或者图来描述网络数据的结构，一个标准的网络模型应该包含节点(Nodes)和以及节点之间的某种连接关系-边(Edges)。所谓社区(Community)，指的是网络中具有某种相似特征的节点构成的隐含群组。而这种隐含的群组归属会使得同一社区内部的节点更易发生连接，即同一社区内节点之间连接的边的数目会更加多；反之，分属不同社区的节点之间则不易发生连接，即不同社区内节点之间连接的边的数目会较少。例如，在同一个区域的社交网络用户彼此更易相互关注，具有相同爱好的社交网络用户彼此更易相互关注等等。而对这种隐含群组的识别可能有助于进行个性化推荐、金融风险管理、基因组识别等等。
在过去的几十年中，学者们对社区检测问题进行了详细而深入的研究，并因此产生了一系列理论工作。从社区检测的算法角度来看，早期的社区检测算法从图本身的结构出发，对边进行分割或者对节点进行聚类，比较著名的一些方法包括谱二分法，Kernighan-Lin算法，Girvan-Newman算法和谱聚类算法等等；基于模块度(Modularity)优化是目前研究和应用最为广泛的的社区检测算法，模块度的概念最先由Newman提出，它采用贪心算法进行对节点进行聚合。此后有一系列学者提出基于模块度优化的算法。从社区检测的统计推断角度来看，随机块模型是目前研究最为广泛和深入的网络模型，该模型假设来自同一社区的节点具有更大的连接概率，反之，来自不同社区的节点应该具有更小的连接可能性。此后一系列学者对此模型进行了改进和拓展。另一个经典的统计模型是由Handcock et al.提出的潜在空间模型。该模型假设节点位于潜在空间中，并且如果它们的潜在位置更接近，则更有可能连接。对社区检测更加全面细致的综述可以详见我们公众号的往期推文《社区发现算法综述》, 《动态社区发现算法综述》等等。
在大规模数据分析的背景下，传统的社区检测方法在处理大规模网络时可能面临巨大的计算挑战。以世界上最大的社交网络平台Facebook为例，其全球注册用户超过10亿人。新浪微博是国内，日均活跃用户也超过2亿人。对于大规模网络，传统方法在计算成本上面临很大的困扰。为了解决这个问题，我们探究一种基于随机投影的大规模网络社区检测算法。
2. 算法介绍
假设网络中一共有个节点，以来编号。这些节点的网络结构关系可以用网络的邻接矩阵来描述。其中，如果第个节点和第个节点存在连接，则；反之, 。若网络为无向图，则我们有，若网络为有向图，则我们认为第个节点和第个节点的关系是有方向的，此时和可能并不相同。令表示第个节点的度(Degree)，并用表示节点的度构成的对角矩阵。接下来，我们假设所有的节点可以被划分到个两两不交的社区中，以编号。令表示第个节点所属的社区编号，我们假设表示第个社区中的样本量，则立刻可以得到. 我们的目标就是基于邻接矩阵来推断其背后的社区结构和每个节点的所属社区。
2.1 一个直观的例子
为了说明随机投影算法，我们首先考虑一个简单但直观的例子。假设整个网络只有个社区且每个社区内包含的节点数相同()。不失一般性，我们假设前个节点属于第一个社区，后个节点属于第二个社区。进一步，我们考虑一个理想情形：假设社区内部的所有节点之间均有边相连，而不同社区的节点之间没有任何边相连。我们首先生成一个随机投影方向，其中每一个元素都是服从标准正态分布的随机变量的实现。进一步，我们可以计算投影向量。通过简单的计算可知，若，则；若，则。可以发现，来自相同社区的节点对应相同的投影，而来自不同社区的节点则对应不同的投影。这启发我们可以通过随机投影对邻接矩阵的信息进行降维压缩，从而达到节省计算成本的目的。当然在实际的问题中，我们不可能遇到这么理想的情况，同一社区内部的节点的之间的连接可能没有这么紧密，同时由于社区外部的节点数目较多，极有可能累计较大的投影噪音。因此这也需要我们探究投影后的矩阵具有怎样的理论性质。
2.2 算法结构
我们首先给出算法的框架描述：
Step.0: 算法的输入为邻接矩阵，随机投影维度，给定的社区数目。
Step.1: 从某一分布中生成随机矩阵。
Step.2: 计算投影邻接矩阵。
Step.3: 将作为特征进行聚类学习，例如使用-means算法
Step.4: 输出聚类结果。
上述框架的想法非常直观，我们通过随机投影对邻接矩阵的信息进行聚合。为了达到节省计算成本的目的，我们期待投影维度，再此基础上一些简单有效的聚类算法可以被用来解决大规模网络的社区检测问题。上述算法主要分为两步：第一步为计算投影矩阵，对于较为稠密的矩阵，这一步付出的计算成本约为，若网络本身为稀疏的，则计算复杂度可进一步降低为，其中表示网络中边的数目；第二步为对投影邻接矩阵进行聚类，若采用经典的-means算法，这一步付出的计算成本约为，若结合更加快速的聚类方法，则计算复杂度可进一步降低。作为对比，我们使用谱聚类方法时要付出的计算复杂度约为。
3. 理论性质
在给出随机投影的算法框架后，我们进一步关心算法的理论性质。具体而言，我们首先需要研究投影后的邻接矩阵自身的性质：不同节点对应的投影向量具有怎么样的性质，它们是否具备被区分的能力？然后是算法识别的一致性，也即当时，是否能以概率1正确识别所有节点的对应社区(强一致性)或者节点的错判率趋于0(弱一致性)。
为了研究理论性质，我们考虑最为经典的随机块模型(Stochastic Block Model, SBM)。假设随机块模型中的网络大小为，社区数目为。邻接矩阵的元素满足，其中来自总体概率矩阵。令\in {1,2,...,K}表示第个节点对应的社区，根据随机块模型假设，我们可知，其中来自社区概率矩阵。由定义可知，是阶对称矩阵。为了研究投影邻接矩阵的若干性质，我们需要给出如下的假设：
令表示平均社区大小，则存在常数 使得社区大小满足 ；
存在常数 和与 有关的数 使得连接概率满足，其中，随着 的发散满足。进一步，我们假设 随着 的发散满足 。
假设要求不同的社区之间的大小是同阶可比的，而假设要求社区内部的连接概率也是同阶可比的，强度至少要大于 的阶；而社区外部的连接概率较小，且满足对角占优的性质。这些假设均可以在过去的文献中被找到。
接下来，我们考虑节点的投影向量之间的性质。理想情况下，我们希望投影向量能够依照节点所属的社区被很好的区分开。具体来说，注意到 表示第 个节点对应的投影向量，对于每一个社区，我们可以计算社区对应的投影向量的中心 , 。接下来，我们计算第 个节点的投影向量到第 个社区的中心向量的距离 。显然，我们希望每一个节点对应的投影向量都距离它所属社区的中心更近，且远离其他社区的中心。用数学的语言来描述这件事情，就是 对所有的 成立。因此，我们可以将感兴趣的问题转化为对事件 的研究。
为了研究事件 的概率，我们首先考虑研究 的性质。具体来说，我们分别探究 的期望和方差的性质。对于 我们有如下结论：
命题1 若假设 和 成立, 对给定的投影维度 ，假设投影矩阵 的每个元素均为标准正态分布的独立同分布观测。 则对任意的节点 满足 我们有：
由命题1，我们可以发现对任意的节点 ，其投影向量与其真实所属社区中心的距离天然小于其与其他社区中心的距离。它们的差值主要由 所决定，可以看到它依赖于两个社区的自己的信息，在命题假设下差值约为 。此外我们发现当随机投影 越大时，期望的差值也越大，这似乎意味着 越大，之间越容易被区分开。但我们需要考虑另外一个问题，当 增大时， 的方差可能也在增大，在这种情况下 是否更加容易识别依然是一个问题。因此，我们接下来研究一下方差的性质，对于 我们有如下结论：
命题2 若假设 和 成立, 对给定的投影维度 ，假设投影矩阵 的每个元素均为标准正态分布的独立同分布观测。 则对任意的节点 满足 我们有：
由命题2， 我们可以发现 的方差随着 和 的发散而变大。在定理假设下，我们可以得到方差的阶约为 。因而，标准差的阶约为 。注意到我们在命题1的分析中得到期望差值的阶约为 ，它的阶比标准差的发散速度更快，因此当 和 发散的时候，我们更能区分不同的 。对于投影维度 来说，在计算能力允许的情况下应当越大越好。下面，我们建立关于事件 的结论。
定理1 若假设 和 成立, 对给定的投影维度 ，假设投影矩阵 的每个元素均为标准正态分布的独立同分布观测。 则我们有
其中 是一个与 无关的正常数。根据定理1的结论可知，若我们采用 -means 算法来对 进行聚类，则当 的时候，我们可以建立算法的强一致性。可以看出，使得 的主要驱动因素来自 ，我们接下来分别讨论这两个因素。首先，若投影维度 充分大使得 ，则此时算法的强一致性受限于网络本身的性质。在满足假设 中， 的的假设下，我们显然可以得到 。接下来，我们考虑 的情形。 如果 ，则我们立刻可得 投影维度 即可，这是一个令人满意的结论。而当 时，为了满足强一致性，我们需要投影维度 。我们考虑两个特殊情况，一个是当 时，我们可得需要的投影维度 ，这可能会带了非常高昂的计算成本；另一个情形是，我们固定投影维度 ，其中 。则我们得到满足强一致性所需要的信号强度为 ，这是一个经典结果要求更高一些的结论。上述两个例子说明，当网络较为稀疏时，我们需要更多的投影维度或更强的连接概率强度来保证强一致性。
5. 小结
我们在本文中介绍了一种基于随机投影的大规模网络社区检测算法，该算法的思路较为简单直观，它首先将网络的邻接矩阵投影到一个低维空间，随后对低维的投影向量进行聚类。进一步，我们给出了一些简单的理论分析来说明投影向量的性质和该算法的使用范围。我们发现该算法还是具有一定的局限性的，对于大规模稀疏网络并不能起到减少计算成本的作用，不过这也可以作为新的起点去思考如何改进来提升算法的性能。值得一提的时，随机投影方法同样可以与谱聚类方法所结合，使用Randomized SVD的技术，我们便可以将谱聚类算法的计算成本大大降低。由于笔者水平有限，在归纳整理和写作的过程中难免出现错误和疏漏，希望各位读者批评指正。
参考文献
[1] Abbe, E. (2018). Community detection and stochastic block models. Foundations & Trends in Communications & Information Theory 14.
[2] Adamic, L. A. and Glance, N. (2005). The political blogosphere and the 2004 U.S. election: divided they blog. In Proceedings of the 3rd International Workshop on Link Discovery 36–43. Association for Computing Machinery.
[3] Amini, A. A., Chen, A., Bickel, P. J. and Levina, E. (2013). Pseudo-likelihood methods for community detection in large sparse networks. The Annals of Statistics 41 2097-2122.
[4] Arthur, D. and Vassilvitskii, S. (2007). K-means++: The advantages of careful seeding. In SODA ’07.
[5] Bickel, P. J. and Chen, A. (2009). A nonparametric view of network models and Newman-Girvan and other modularities. Proceedings of the National Academy of Sciences 106 21068-21073.
[6] Bickel, P. J. and Sarkar, P. (2016). Hypothesis testing for automated community detection in networks. Journal of the Royal Statistical Society. Series B : Statistical Methodology 78 253–273.
[7] Clauset, A., Newman, M. and Moore, C. (2006). Finding community structure in very large networks. Physical Review E 70 066111. [8] De, Meo, P., Ferrara, E., Provetti, A., Fiumara and G. (2014). Mixing local and global information for community detection in large networks (Conference Paper). Journal of Computer and System Sciences.
[9] Gao, C., Ma, Z., Zhang, A. Y. and Zhou, H. H. (2018). Community detection in degree-corrected block models. The Annals of Statistics 46 2153 - 2185.
[10] Handcock, M. S., Raftery, A. E. and Tantrum, J. M. (2007). Model-based clustering for social networks. Journal of the Royal Statistical Society. Series A: Statistics in Society 170 301-354.
[11] Holland, P. W., Laskey, K. B. and Leinhardt, S. (1983). Stochastic blockmodels: First steps. Social Networks 5 109-137.
[12] Hu, J., Qin, H., Yan, T. and Zhao, Y. (2020). Corrected Bayesian information criterion for stochastic block models. Journal of the American Statistical Association 115 1771-1783.
[13] Huang, D., Yin, J., Shi, T. and Wang, H. (2016). A statistical model for social network labeling. Journal of Business & Economic Statistics 34 368-374.
[14] Newman, M. and Girvan, M. (2004). Finding and evaluating community structure in networks. Physical Review E 69 026113.
[15] Newman, M. E. J. (2004). Fast algorithm for detecting community structure in networks. Physical Review E 69 066133.
[16] Qin, T. and Rohe, K. (2013). Regularized spectral clustering under the degree-corrected stochastic block model. advances in neural information processing systems.
[17] Riedy, J., Bader, D. A. and Meyerhenke, H. (2012). Scalable multi-threaded community detection in social networks. In 2012 IEEE 26th International Parallel and Distributed Processing Symposium Workshops PhD Forum 1619-1628.
[18] Rohe, K., Chatterjee, S. and Yu, B. (2010). Spectral clustering and the high-dimensional stochastic blockmodel. The Annals of Statistics 39 1878-1915.
[19] Sojourner, A. (2013). Identification of peer effects with missing peer data: evidence from project STAR. Economic Journal 123.
[20] Su, L., Wang, W. and Zhang, Y. (2017). Strong consistency of spectral clustering for stochastic block models. Economics and Statistics Working Papers.
[21] Wainwright, M. J. (2019). High-dimensional statistics: A nonasymptotic viewpoint. Cambridge University Press.
[22] Zhao, Y., Levina, E. and Zhu, J. (2012). Consistency of community detection in networks under degree-corrected stochastic block models. The Annals of Statistics 40 2266–2292.